#include <bitset>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

const int kMaxN = 12;
const int kInf = 1e9;

vector<pair<int, int>> g[1 << kMaxN];
int dist[1 << kMaxN];

void Dijkstra(int n, int s) {
  priority_queue<pair<int, int>> pq;

  fill(dist, dist + n, kInf);
  dist[s] = 0;
  pq.emplace(-dist[s], s);
  while (!pq.empty()) {
    int d = -pq.top().first, u = pq.top().second;

    pq.pop();
    if (dist[u] != d) {
      continue;
    }
    for (const pair<int, int> &e : g[u]) {
      int v = e.first;

      if (dist[v] > d + e.second) {
        dist[v] = d + e.second;
        pq.emplace(-dist[v], v);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; t--) {
    int n, m, s;
    string str;

    cin >> n >> m >> str;

    for (int i = 0; i < (1 << n); i++) {
      g[i].clear();
    }
    bitset<kMaxN> s_t(str);
    s = s_t.to_ulong();
    for (int i = 0; i < m; i++) {
      int d;
      string s1, s2;

      cin >> d >> s1 >> s2;
      bitset<kMaxN> e1(s1), e2(s2);

      e1 ^= ((1 << n) - 1);

      int tmp1 = e1.to_ulong(), tmp2 = e2.to_ulong();
      for (int u = 0; u < (1 << n); u++) {
        int v = (u & tmp1) | tmp2;

        g[u].emplace_back(v, d);
      }
    }
    Dijkstra(1 << n, s);
    if (dist[0] == kInf) {
      cout << "-1\n";
    } else {
      cout << dist[0] << "\n";
    }
  }
  return 0;
}